Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:

You may assume that duplicates do not exist in the tree.

Solution:

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. public class Solution {
  11.   public TreeNode buildTree(int[] preorder, int[] inorder) {
  12.     Map<Integer, Integer> map = new HashMap<>();
  14.     for (int i = 0; i < inorder.length; i++) {
  15.       map.put(inorder[i], i);
  16.     }
  18.     return build(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1, map);
  19.   }
  21.   TreeNode build(int[] pre, int i1, int j1, int[] in, int i2, int j2, Map<Integer, Integer> map) {
  22.     if (i1 > j1 || i2 > j2) {
  23.       return null;
  24.     }
  26.     TreeNode root = new TreeNode(pre[i1]);
  28.     int index = map.get(root.val);
  29.     int nleft = index - i2;
  31.     root.left = build(pre, i1 + 1, i1 + nleft, in, i2, index - 1, map);
  32.     root.right = build(pre, i1 + nleft + 1, j1, in, index + 1, j2, map);
  34.     return root;
  35.   }
  36. }